#include <iostream>
#include <vector>

class Solution {
public:
    int Getkey(std::vector<int>& nums, int left, int right)
    {
        int mid = (right - left) / 2 + left;
        int minnum = std::min(std::min(nums[left], nums[right]), nums[mid]);
        int maxnum = std::max(std::max(nums[left], nums[right]), nums[mid]);
        if (minnum != nums[left] && maxnum != nums[left])
            return left;
        if (minnum != nums[right] && maxnum != nums[right])
            return right;
        return mid;
    }

    void QuickSort(std::vector<int>& nums, int left, int right)
    {
        if (left >= right)
            return;
        std::swap(nums[Getkey(nums, left, right)], nums[left]);
        int begin = left, end = right;
        int key = begin;
        while (begin < end)
        {
            while (begin < end && nums[end] >= nums[key])
                end--;

            while (begin < end && nums[begin] <= nums[key])
                begin++;
            std::swap(nums[begin], nums[end]);
        }
        std::swap(nums[begin], nums[key]);
        QuickSort(nums, left, begin - 1);
        QuickSort(nums, begin + 1, right);
    }

    std::vector<int> sortArray(std::vector<int>& nums) {
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main()
{
    std::vector<int> v = { 110, 100, 0 };
	Solution s;
    s.sortArray(v);
	for (auto i : v)
		std::cout << i << " ";
    return 0;

}